package bitmap

import (
	"bytes"
	"encoding/gob"
)

/*
每个uint64类型有64位（8字节），可以表示64个连续整数的存在状态。
位图本质是将整数空间划分为多个uint64块，每个块管理64个连续数值。

示例：
存储数值n=123时：
第1个uint64管理 0-63
第2个uint64管理 64-127
第3个uint64管理 128-191
依此类推...

因此：
块索引 = n / 64（确定属于哪个uint64）
位偏移 = n % 64（确定在块内的具体bit位）
*/

/*
(1) 计算块索引：index = num >> 6
等价于：num / 64
原理：右移6位相当于除以2⁶（即64）
例：123 >> 6 = 1（二进制01111011右移6位得00000001）

(2) 计算位偏移：offset = num & 0x3F
等价于：num % 64
原理：0x3F是二进制00111111，与操作相当于取最后6位
例：123 & 0x3F = 59（二进制01111011 & 00111111 = 00111011）
*/

type bitmap struct {
	data []uint64 // 每个uint64存储64位
	max  uint64   // 支持的最大数值
}

// max: 支持的最大数值
func NewBitmap(max uint64) *bitmap {
	/*
		需求：存储从 0 到 maxValue 的所有整数（共 maxValue + 1 个数值）。
		每个uint64块管理64个数值（如块0管理0-63，块1管理64-127，依此类推）。

		e.g: maxValue = 64 → 需要存储0-64（共65个数），需2个块
	*/
	size := (max + 64) >> 6
	return &bitmap{
		data: make([]uint64, size),
		max:  max,
	}
}

func (bm *bitmap) Add(num uint64) {
	if num > bm.max {
		// 需要扩容
		newMax := num + num/4 // 扩容25%余量
		bm.expand(newMax)
	}
	index := num >> 6    // 相当于 num/64
	offset := num & 0x3F // 相当于 num%64

	/*
		1 << offset：生成仅在目标位置1的掩码
		例：offset=3 → 00000000...00001000

		按位或(|)：将目标位设为1，不影响其他位
	*/
	bm.data[index] |= 1 << offset
}

func (bm *bitmap) Contains(num uint64) bool {
	if num > bm.max {
		return false
	}
	index := num >> 6
	offset := num & 0x3F
	/*
		按位与(&)：屏蔽非目标位，仅保留目标位状态
		结果判断：若结果非0，说明目标位是1（存在）
	*/
	return (bm.data[index] & (1 << offset)) != 0
}

func (bm *bitmap) Remove(num uint64) {
	if num > bm.max {
		return
	}
	index := num >> 6
	offset := num & 0x3F
	/*
		&^ 是位清除运算符（AND NOT）
		等价于：bm.data[index] = bm.data[index] & ^(1 << offset)
		效果：只清除目标位，保留其他位
	*/
	bm.data[index] &^= 1 << offset // 位清除操作
}

// 使用Run-Length Encoding压缩
func (bm *bitmap) Compress() []byte {
	var buf bytes.Buffer
	encoder := gob.NewEncoder(&buf)
	encoder.Encode(bm.data)
	return buf.Bytes()
}

// 动态扩展
func (bm *bitmap) expand(newMax uint64) {
	newSize := (newMax + 64) >> 6
	if newSize > uint64(cap(bm.data)) {
		newData := make([]uint64, newSize)
		copy(newData, bm.data)
		bm.data = newData
	}
	bm.max = newMax
}

// 解压缩
func Decompress(data []byte) *bitmap {
	var arr []uint64
	buf := bytes.NewReader(data)
	decoder := gob.NewDecoder(buf)
	decoder.Decode(&arr)
	return &bitmap{data: arr, max: uint64(len(arr)*64 - 1)}
}
